package LC;

/**
 * https://leetcode.com/problems/longest-palindromic-substring/description/
 * Given a string s, find the longest palindromic substring in s.
 * You may assume that the maximum length of s is 1000.
 * Example:
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 * Example:
 * Input: "cbbd"
 * Output: "bb"
 */
public class LC_005_LongestPalindromicSubstring_TwoPointers {
    public static void main(String[] args) {
        String s = "aaabbbaaaz";
        System.out.println(longestPalindrome(s));
    }

    private static String longestPalindrome(String s) {
        String result = null;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            int st = i;
            int en = i + 1;
            while (st >= 0 && en <= s.length() - 1 && s.charAt(st) == s.charAt(en)) {
                st--;
                en++;
            }
            if (en - st - 1 > max) {
                max = en - (st + 1);
                result = s.substring(st + 1, en - 1 + 1);
            }

            st = i - 1;
            en = i + 1;
            while (st >= 0 && en <= s.length() - 1 && s.charAt(st) == s.charAt(en)) {
                st--;
                en++;
            }
            if (en - st - 1 > max) {
                max = en - st - 1;
                result = s.substring(st + 1, en - 1 + 1);
            }
        }
        return result;
    }

    static class Solution {
        public String longestPalindrome(String s) {
            if (s.isEmpty()) return null;
            if (s.length() == 1) return s;
            String longest = s.substring(0, 1);
            for (int i = 0; i < s.length(); i++) {
                String tmp = helper(s, i, i);
                longest = (tmp.length() > longest.length()) ? tmp : longest;

                tmp = helper(s, i, i + 1);
                longest = (tmp.length() > longest.length()) ? tmp : longest;
            }
            return longest;
        }

        private static String helper(String s, int begin, int end) {
            while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
                begin--;
                end++;
            }
            return s.substring(begin + 1, end);
        }
    }
}
